package com.executor;

import java.util.Arrays;
import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.RecursiveAction;
/**
 *
 * 功能描述: 通过fork/join快速排序
 *
 * @param:
 * @return:
 * @auther: csh
 * @date: 2023/4/17 9:54 下午
 */
public class QuickSort extends RecursiveAction {

    private static final int THRESHOLD = 1000;  // 阈值，当待排序数组大小小于该值时不再进行拆分
    private int[] arr;
    private int start;
    private int end;

    public QuickSort(int[] arr, int start, int end) {
        this.arr = arr;
        this.start = start;
        this.end = end;
    }

    @Override
    protected void compute() {
        if (end - start <= THRESHOLD) {  // 如果待排序数组大小小于阈值，直接进行快速排序
            Arrays.sort(arr, start, end);
        } else {   // 如果待排序数组大小大于阈值，拆分为两个任务并执行
            int pivot = partition();
            QuickSort left = new QuickSort(arr, start, pivot);
            QuickSort right = new QuickSort(arr, pivot + 1, end);
            left.fork();
            right.fork();
            left.join();
            right.join();
        }
    }

    private int partition() {   // 快速排序的分区函数
        int pivot = arr[start];
        int i = start - 1;
        int j = end;
        while (true) {
            do {
                i++;
            } while (arr[i] < pivot);
            do {
                j--;
            } while (arr[j] > pivot);
            if (i >= j) {
                return j;
            }
            swap(i, j);
        }
    }

    private void swap(int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int N = 1000000;
        int[] arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = (int) (Math.random() * 100);
        }
        ForkJoinPool pool = new ForkJoinPool();
        pool.invoke(new QuickSort(arr, 0, arr.length));
        System.out.println(Arrays.toString(arr));
    }

}
